This invention relates to digital integrated circuit memories; and more particularly, it relates to architectures for such memories which enable a digital computer to perform various bookkeeping operations at a very high speed.
In the prior art, digital integrated circuit memories have been extensively used in data processing systems. These memories are broadly classified as RAMs, ROMs, or CAMs. Each such memory includes a plurality of storage cells; but, each such memory also has a unique overall architecture which differentiates it from the other memories.
In a RAM memory, the storage cells are arranged on a chip as an array f row and columns, and control lines are provided which enable data to be written into and read from the cells one row at a time. RAMs are particularly useful where data words need to be written and read in any sequence from rows that are selected randomly.
In a ROM memory, the storage cells are again arranged on a chip as an array of rows and columns; however, the data is either permanently written into the cells, or the data can only be rewritten off-line. Also, a ROM cell occupies less chip space then a RAM cell; and thus, a ROM memory chip can contain more cells then a RAM memory chip. ROM memories are particularly useful for storing large amounts of fixed digital information, such as thousands of computer instructions.
In a CAM memory, the memory cells are again arranged as an array of rows and columns; and control lines are provided which enable data to be written into the cells one row at a time. In addition, a comparator is provided with each row of cells, and input lines are provided which carry input signals to each of the comparators. In operation, those input signals are compared to the data in each row of memory cells, and output signals are generated which indicate whether or not a match occurs. CAM memories are particularly useful in data caches and instruction caches.
One common feature of the above prior art memories is that data in each memory is always read, or written, or compared row by row. However, such row oriented operations are not well suited for performing certain bookkeeping functions in which various relationships between two sets of items continuously change and need to be tracked These bookkeeping functions are explained more fully herein in the Detailed Description.
Accordingly, a primary object of the present invention is to provide a memory having a novel architecture which efficiently performs bookkeeping functions with high speed.